/*single cycle list 单循环链表

	第二版
	添加泛型化处理
*/

#include<iostream>
using namespace std;
#include<assert.h>
//
//定义节点
//
template<typename T>
struct node_of_list
{
	int size;  // 标记位置
	T   data;  //添加模版项
	struct node_of_list<T>* next;
}; //Templates are not allowed in typedef definitions.
template<typename T>
using node = node_of_list<T>;
template<typename T>
using n_ptr = node_of_list<T>*;
//
//泛型变量初始化
//
struct data_save{
	int price;
}ds;
int ds_init()
{
	return rand()%1000;
}
//
//初始化
//
template<typename T>
n_ptr<T> cycle_list()
{
	n_ptr<T> firstnode = new node<T>();
	firstnode->size = 0;
	firstnode->data = ds_init();
	firstnode->next = firstnode;
	return firstnode;//头指针
}
template<typename T>
n_ptr<T> cycle_list(int num_of_node)
{
	n_ptr<T> firstnode = cycle_list<T>();
	n_ptr<T> temp_ptr=firstnode;
	if (num_of_node >= 2){
		for (int i = 1; i < num_of_node; i++){
			n_ptr<T> node1 = new node<T>();   // 存在堆上需要delete？？？
			node1->size = i;
			node1->data = ds_init();
			node1->next = firstnode;
			//连接
			temp_ptr->next = node1;
			temp_ptr = node1;
		}
	}
	return firstnode;
}
//
//     显示 输出循环链表内容
//
template<typename T>
void print(n_ptr<T> &temp_ptr)
{
	cout << temp_ptr->data << ":" << temp_ptr->size << endl;
	//cout << temp_ptr->data << ":" << temp_ptr->size << " ";
}
template<typename T>
void show_cycle_list(n_ptr<T> firstnode)
{
	n_ptr<T> temp_ptr = firstnode->next;
	int count = 1;
	print(firstnode);
	while (temp_ptr != firstnode){
		print(temp_ptr);
		temp_ptr = temp_ptr->next;
		if (count % 5 == 0){
			count = 0;
			cout << endl;
		}
		count++;
	}
}
//
//基本操作：插入
//
template<typename T>
bool insert_front(int num,n_ptr<T> &firstnode)
{
	// 初始化节点
	n_ptr<T> node1 = new node<T>();
	assert(node1!=NULL);
	int number = firstnode->size;
	node1->data = ds_init();
	node1->size = --number;//头插的情况下减少1
	// 插入链表中
	n_ptr<T> tempnode = firstnode;//子函数中的指针不用手动释放。
	firstnode = node1;
	firstnode->next = tempnode;
	//更改尾指针
	while (tempnode->next!=firstnode->next)
	{
		tempnode = tempnode->next;
	}
	tempnode->next = firstnode;
	return true;
}
template<typename T>
bool insert_back(int num, n_ptr<T> &firstnode)
{
	//找到尾节点
	n_ptr<T> tempnode=firstnode;
	while (tempnode->next != firstnode){
		// 找到尾节点
		tempnode = tempnode->next;
	}
	//初始化待插入节点
	n_ptr<T> node1 = new node<T>();
	assert(node1 != NULL);
	node1->data = ds_init();
	int number = tempnode->size;
	node1->size = ++number;//尾插的情况下加1
	//插入链表中
	tempnode->next = node1;
	node1->next = firstnode;
	return true;
}
//
//基本操作：删除
//
template<typename T>
bool del_list(n_ptr<T> &firstnode)//清空链表
{
	n_ptr<T> tempnode = firstnode,tempnode1;
	while (tempnode->next!=firstnode){
		tempnode1 = tempnode;
		tempnode = tempnode->next;
		delete tempnode1;
	}
	delete tempnode;
	return true;
}
template<typename T>
bool del_node(int value, n_ptr<T> firstnode)//去掉一个节点
{
	//找到要删除节点
	n_ptr<T> tempnode = firstnode;
	while (tempnode->size!=value)
	{
		tempnode = tempnode->next;
		if (tempnode == firstnode){
			break;
		}
	}
	//查找 待删除节点的上一个节点
	while (firstnode->next != tempnode){
		firstnode=firstnode -> next;
	}
	firstnode->next = tempnode->next;
	delete tempnode;
	return true;
}
bool del_list(int condition)//按条件删除
{
	return true;
}
//
//基本操作：修改节点内容
//
bool change_content()
{
	return true;
}
//
//基本操作:查找指定内容。
//
template<typename T>
bool find_content(int value, n_ptr<T> firstnode)
{
	n_ptr<T> tempnode = firstnode;
	while (tempnode->size!=value)
	{
		tempnode = tempnode->next;
		if (tempnode == firstnode){
			break;
		}
	}
	if (tempnode->size == value){
		return true;
	}
	else{
		return false;
	}
	return true;
}
//
//测试循环链表
//
template<typename T>
void test_cycle_list()
{
	n_ptr<int> list = cycle_list<int>(10);
	srand(199);
	for (int i = 0; i < 5;i++){
		int number = rand();
		insert_front(number,list);
		insert_back(number,list);
	}
	cout << "构建完成"<<endl;
	bool isfind=find_content(3,list);
	cout << "找到了：" << isfind << endl;

	del_node(3,list);

	show_cycle_list(list);

	bool right_run=del_list(list);
	if (right_run){
		cout << "列表成功删除。" << endl;
	}
	else{
		cout << "列表删除失败。";
	}
}